package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 234. 回文链表
 * @since 2024/2/2 17:22
 */
public class IsPalindrome234 {
    // 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
    // 如果是，返回 true ；否则，返回 false 。
    // 1 -> 2 -> 1
    // 1 -> 2 -> 3 -> 1

    /**
     * 优化
     * 解：
     * 1.求中间节点的时候，同时反转链表前半部分
     * 2.将反转的链表与后半部分比较，只要有一个不一样就false
     * 3.基数链表要特殊处理
     */
    public boolean isPalindrome(ListNode head) {
        // 慢指针，中间点
        ListNode p1 = head;
        // 快指针
        ListNode p2 = head;
        // 旧头
        ListNode o1 = head;
        // 反转链表新头
        ListNode n1 = null;
        while (p2 != null && p2.next != null) {
            // 快慢指针移动
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }

        // 基数链表节点特殊处理，让p1节点后移
        if (p2 != null) {
            p1 = p1.next;
        }

        // 比较
        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            n1 = n1.next;
            p1 = p1.next;
        }

        return true;
    }


    /**
     * 未优化
     * 解：
     * 1：求出中间链表
     * 2：反转中间链表
     * 3：将新链表逐一和原链表进行比较，只要有一个不一样就false
     */
    public boolean isPalindrome02(ListNode head) {
        ListNode middle = middle(head);
        ListNode newHead = reverse(middle);
        while (newHead != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }

    // 求中间链表
    private static ListNode middle(ListNode head) {
        // 慢指针，中间点
        ListNode p1 = head;
        // 快指针
        ListNode p2 = head;

        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }

        return p1;
    }

    // 反转链表
    private static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 前驱
        ListNode o1 = head;

        ListNode n1 = null;
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }
}
